#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""




class OptimalBinarySearchTree():
    def __init__(self, eles):
        self.eles = eles
        self.len = len(eles)
        self.init_data()
        self.calc()

    def init_data(self):
        row = [0] * self.len
        self.value_mat = [list(row) for i in range(self.len)]
        self.root_mat = [list(row) for i in range(self.len)]

        for i in range(self.len):
            self.value_mat[i][i] = self.eles[i][1]
            self.root_mat[i][i]  = self.eles[i][0]

    def calc(self):
        for tree_num in range(1, self.len):
            # 5, 4, 3, 5-1 = 4
            for left in range(0, self.len-tree_num):
                right = left + tree_num
                value, root = self.range(left, right)
                self.value_mat[left][right] = value
                self.root_mat[left][right]  = root

    def range(self, left, right):
        if left == right:
            return self.eles[left][1], left     # value, root

        min = 99999
        for mid in range(left, right+1):
            # value = self.get_value[left][mid-1] + self.value_mat[mid+1][right] + self.weight_sum(left, right)
            # 这里使用weight_sum: 因为加上根节点后, [left, right]中所有节点(包括root)深度加深1级. 增加的次数, 刚好是[left, right]次数之和
            value = self.get_value(left, mid-1) + self.get_value(mid+1, right) + self.weight_sum(left, right)
            if value < min:
                min = value
                min_root = mid
        return min, min_root

    def get_value(self, left, right):
        # 这里可以通过矩阵多初始化左边和上面一行来规避此函数的right < left判断(防止越界index out of bound)
        if right < left:
            return 0
        return self.value_mat[left][right]

    def weight_sum(self, left, right):
        # TODO: sum需要优化
        return sum(e[1] for e in self.eles[left:right+1])

    def __str__(self):
        return str(self.value_mat) + "\n" + str(self.root_mat)


def test():
    # eles = [(1, 3), (2, 4), (3, 2), (4, 7), (5, 2)]

    # 第0个是根节点的value, 第1个是搜索次数(可以转换为频率)
    eles = [(10, 4), (12, 2), (16, 6), (21, 3)]

    ob = OptimalBinarySearchTree(eles)
    print(ob)


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
